package com.jz;

/**
 * Description: JZ31 栈的压入、弹出序列
 *
 * @author weiruibai.vendor
 * Date: 2022/9/22 14:07
 */
public class JZ31 {

    /**
     * [1,2,3,4,5],[4,5,3,2,1] true
     * [1,2,3,4,5],[4,3,5,1,2] false
     * [1,2,3,4,5],[1,2,3,4,5] true
     * [1,2,3,4,5],[3,5,4,2,1] true
     * [1,2,3,4,5],[1,4,3,5,2] true
     *
     * @param args
     */
    public static void main(String[] args) {
        JZ31 jz31 = new JZ31();
        int[] pushA = {1, 2, 3, 4, 5};
        int[] popA = {4, 5, 3, 2, 1};
        popA = new int[]{4, 3, 5, 1, 2};

        pushA = new int[]{1};
        popA = new int[]{2};
        ////////
        pushA = new int[]{1, 2, 3, 4, 5};
        popA = new int[]{1, 2, 3, 4, 5};
        ////////
        pushA = new int[]{1, 2, 3, 4, 5};
        popA = new int[]{3, 5, 4, 2, 1};
        ////////
        pushA = new int[]{1, 2, 3, 4, 5};
        popA = new int[]{1, 4, 3, 5, 2};
        System.out.println(jz31.IsPopOrder(pushA, popA));
    }

    /**
     * 思路
     * 1、找到popA第一个弹出的值在pushA的位置k，然后以k的中心分别讨论
     * 2、
     * 2.1 当k是pushA的第一个节点是（下标是0），那么popA的下一个只能是pushA后面未被使用过的值
     * 2.2 当k是pushA的最后一个节点时，那么popA的下一个值只能在pushA前面第一个未被使用过的值（注意：第一个未被使用过的值！！！！）
     * 2.3 当k是一般位置的值时，情况1，popA的下一个值在k的左侧第一个未被使用过的值，情况2，popA的下一个值在k的右侧未被使用的值（不一定是第一个！！）
     * 注意几个场景
     *
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        boolean[] used = new boolean[pushA.length];
        int N = popA.length;
        int k = 0;
        // 找到第一个等于弹出的位置下标
        while (k < N && popA[0] != pushA[k]) {
            k++;
        }
        if (k >= N) {
            return false;
        }
        used[k] = true;
        for (int i = 1; i < N; i++) {
            // k在末尾，那只能是前一个未被使用的
            if (k == N - 1) {
                while (k >= 0 && used[k]) {
                    k--;
                }
                if (pushA[k] != popA[i]) {
                    return false;
                }
            } else if (k == 0) {
                // k在第一位置，那只能是后面一位未被使用的
                while (k < N && used[k]) {
                    k++;
                }
                while (k < N && pushA[k] != popA[i]) {
                    k++;
                }
                if (k >= N) {
                    return false;
                }
            } else {
                int tmp = k;
                // 普通,k的左边未被使用的
                while (tmp >= 0 && used[tmp]) {
                    tmp--;
                }
                if (tmp >= 0 && pushA[tmp] == popA[i]) {
                    k = tmp;
                } else {
                    // k右边未被使用的
                    tmp = k;
                    while (tmp < N && used[tmp]) {
                        tmp++;
                    }
                    while (tmp < N && pushA[tmp] != popA[i]) {
                        tmp++;
                    }
                    if (tmp >= N) {
                        return false;
                    } else {
                        k = tmp;
                    }
                }
            }
            used[k] = true;
        }
        return true;
    }
}
